package hdoj;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class NightmareHDU1072 {

	private static final int OBSTACLE = 0;
	private static final int START = 2;
	private static final int EXIT = 3;
	private static final int RESERT = 4;
	
	private static final int INITAL_MINUTE = 6;
	
	private static final int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	
	private int minMinute = Integer.MAX_VALUE;
	
	private static final int MAX = 10; 
	private int[][] maze = new int[MAX][MAX];
	private int[][] visited = new int[MAX][MAX];
	
	//存储每个点的分钟数
	private int[][] minutes = new int[MAX][MAX];
	//存储从起点到每个点的时间
	private int[][] steps = new int[MAX][MAX];
	
	
	private int rows, columns;
	
	public static void main(String[] args) {
		NightmareHDU1072 object = new NightmareHDU1072();
		object.getRes();
	}
	
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		int startX = 0, startY = 0;
		for (int i = 1; i <= testCase; i++) {
			minMinute = Integer.MAX_VALUE;
			rows = scanner.nextInt();
			columns = scanner.nextInt();
			for(int j = 0; j < rows; j++){
				for (int k = 0; k < columns; k++) {
					maze[j][k] = scanner.nextInt();
					if(maze[j][k] == START){
						startX = j;
						startY = k;
					}
					//注意，这一步不能省，因为后面会判断steps的大小关系
					steps[j][k] = Integer.MAX_VALUE;
					minutes[j][k] = 0;
				}
			}
			minutes[startX][startY] = INITAL_MINUTE;
			steps[startX][startY] = 0;
			dfs(startX, startY);
//			visited[startX][startY] = INITAL_MINUTE;
//			dfs(startX, startY, INITAL_MINUTE, 0);
//			bfs(startX, startY, maze, visited, INITAL_MINUTE, 0);
			if (minMinute == Integer.MAX_VALUE) {
				System.out.println(-1);
			}else{
				System.out.println(minMinute);
			}
		}
		scanner.close();
	}
	
	
	//先使用DFS试试  TLE
	//稍微有点错误，因为这道题可以无限使用REREST,还有一个情况就是
//	1 2 1 1 1 1 1 4 
//	1 0 0 0 1 0 0 1 
//	1 4 1 0 1 1 0 1 
//	1 0 0 0 0 3 0 1 
//	1 1 4 1 1 1 1 1
	//上面的逃离路径应该是 ← ↓ ↓ → ←(而我此时的visited[curX][curY] 为true,导致我不能返回，所以这个返回-1，计算错误
	//将visited数组改为int型，存储到达该点的分钟数
	//如果后续minute > 该值，则可以继续访问
	public void dfs(int x, int y, int minute, int curMinute){
		if(maze[x][y] == EXIT && minute > 0){
			minMinute = Math.min(minMinute, curMinute);
			return;
		}
		//如果此时只有0分钟，不能继续移动了
		if(minute <= 0){
			return;
		}
		// System.out.println("x: " + x + " y : " + y + " minute: " + minute);
		for (int i = 0; i < dir.length; i++) {
			int curX = x + dir[i][0];
			int curY = y + dir[i][1];
			//关键逻辑 (visited[curX][curY] != 0 && visited[curX][curY] >= minute)
			if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || maze[curX][curY] == OBSTACLE 
					|| (visited[curX][curY] != 0 && visited[curX][curY] >= minute) ){
				continue;
			}
			visited[curX][curY] = minute - 1;
			
			if(maze[curX][curY] == RESERT && minute > 0){
				minute = INITAL_MINUTE;
			}
			dfs(curX, curY, minute - 1, curMinute + 1);
			visited[curX][curY] = 0;
		}
	}
	
	
	
	//Runtime 296MS, c++代码 0ms
	public void dfs(int x, int y){
		//如果此时只有0分钟，不能继续移动了
		if(minutes[x][y] <= 0){
			return;
		}
		if(maze[x][y] == EXIT){
			minMinute = Math.min(minMinute, steps[x][y]);
			return;
		}
		for (int i = 0; i < dir.length; i++) {
			int curX = x + dir[i][0];
			int curY = y + dir[i][1];
			if(curX < 0 || curX >= rows || curY < 0 || curY >= columns || maze[curX][curY] == OBSTACLE ){
				continue;
			}
			//感觉跟我写的也就差了这一个条件啊
			// TODO figure out
			//如果步数并且分钟都不优于当前值到该点的值，那么就不走
			if (steps[curX][curY] <= steps[x][y] + 1 && minutes[curX][curY] >= minutes[x][y] - 1){
				continue;
			}
			steps[curX][curY] = steps[x][y] + 1;
			minutes[curX][curY] = minutes[x][y] - 1;
			if(maze[curX][curY] == RESERT && minutes[curX][curY] > 0){
				minutes[curX][curY] = INITAL_MINUTE;
			}
			dfs(curX, curY);
		}
	}
	
	private class Node{
		int x, y, minute, curMinute;
		public Node(int x, int y){
			this.x = x;
			this.y = y;
		}
		
	}
	
	
	//不知道为什么，bfs也不对
	public void bfs(int x, int y, int[][] maze, int[][] visited, int minute, int curMinute){
		Queue<Node> queue = new LinkedList<Node>();
		Node temp = new Node(x, y);
		temp.minute = INITAL_MINUTE;
		temp.curMinute = 0;
		queue.add(temp);
		while(!queue.isEmpty()){
			temp = queue.poll();
			// System.out.println(" x: " + temp.x + " y: " + temp.y + " minute: " + temp.minute);
			if(maze[temp.x][temp.y] == EXIT && minute > 0){
				minMinute = Math.min(temp.curMinute, minMinute);
				continue;
			}
			if(temp.minute <= 0){
				continue;
			}
			if(maze[temp.x][temp.y] == RESERT){
				temp.minute = INITAL_MINUTE;
			}
			for (int i = 0; i < dir.length; i++) {
				int curX = temp.x + dir[i][0];
				int curY = temp.y + dir[i][1];
				// System.out.println(" whyX ：" + curX + " y: " + curY);
				//关键逻辑 (visited[curX][curY] != 0 && visited[curX][curY] >= minute)
				if(curX < 0 || curX >= maze.length || curY < 0 || curY >= maze[0].length ||
						maze[curX][curY] == OBSTACLE ){
//					if(curX >= 0 && curX < maze.length && curY >= 0 && curY < maze[0].length &&
//						maze[curX][curY] != OBSTACLE){
////					System.out.println(" curX " + curX + " curY :" + curY +  
////							"last : " + visited[curX][curY] + " temp minute: " + temp.minute);
//					}
					continue;
				}
				// System.out.println(" nextX ：" + curX + " y: " + curY);
				Node next = new Node(curX, curY);
				next.curMinute = temp.curMinute + 1;
				next.minute = temp.minute - 1;
				if(visited[curX][curY] != 0 && 
						visited[curX][curY] >= next.minute){
					continue;
				}
				visited[curX][curY] = next.minute;
				queue.add(next);
			}
		}
	}
}
